1. Technical Field
At least one example in accordance with the present invention relates generally to systems and methods for solving optimization problems and more specifically to systems and methods used to solve optimization problems that include complex logical relationships between binary variables, which assume only values 0 or 1.
2. Discussion of Related Art
Software packages that are capable of solving optimization problems are known. Optimization problems, which can be used to model the operations of particular physical systems, are usually expressed as terms of an “objective function” and a set of constraints that must be satisfied by a solution. Optimization problems may be formulated to achieve a variety of goals such as minimizing cost, maximizing throughput, or maximizing profit resulting from the provision of physical goods and services. Software packages designed to solve optimization problems use optimization engines, which are also known as solver engines, to determine a solution that maximizes or minimizes the value of the objective function subject to the set of constraints.
There is no single package or product that is able to solve every type of optimization problem. Solver engines differ in type, such as linear, integer, mixed, quadratic and nonlinear convex or nonlinear global, in the number of variables they can support, and in the solution techniques that they employ. One example of a solver engine is ILOG CPLEX which is available from ILOG Inc. of Sunnyvale, Calif. A few of the other solvers include: LINGO which is available from LINDO Systems, Inc. of Chicago Ill., Xpress-MP from Dash Optimization which has offices in the UK and in Engelwood Cliffs, N.J., and the free NEOS server from Argonne National Laboratory, which is operated by the University of Chicago.
These conventional optimization packages support linear constraints. A few specialized packages support both linear and non-linear mathematical constraints. However, logical constraints generally are not integrated into the optimization engine, but instead are enforced by routines outside of the optimization engine which repeatedly test logical constraints against candidate solution values in order to determine whether the logical constraints are satisfied.
Binary variables, which may assume a value of 0 or 1, are used in logical constraints to express the values true or false. The use of binary variables recently has been expanded. They have been introduced to general optimization problems as a way to solve problems whose choice of linear constraints depends on logical rules or relationships between problem variables. Some advanced packages enable an analyst to express these logical relationships in order to activate different sets of linear constraints depending on these relationships. For example, an analyst might indicate that at least one of the following constraints must be imposed.2x1+x2+5x3<=100, 6x1−x2−39x3>=10, x7+18x1 >=25by associating a binary variable with each expression and stipulating that at least one of these variables must be 1 (true).
The CPLEX package has the capability to support simple logical conditions. CPLEX has a proprietary language that can be used to express logical relationships. Simple relationships are imposed on sets of linear constraints by adding new binary variables to the model and expressing the relationships as logical constraints upon these variables.